{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Increments on Subarrays to Form a Target Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #array #dynamic-programming #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #数组 #动态规划 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minNumberOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #形成目标数组的子数组最少增加次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>target</code>&nbsp;和一个数组&nbsp;<code>initial</code>&nbsp;，<code>initial</code>&nbsp;数组与 <code>target</code>&nbsp; 数组有同样的维度，且一开始全部为 0 。</p>\n",
    "\n",
    "<p>请你返回从 <code>initial</code>&nbsp;得到&nbsp; <code>target</code>&nbsp;的最少操作次数，每次操作需遵循以下规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>在 <code>initial</code>&nbsp;中选择 <strong>任意</strong>&nbsp;子数组，并将子数组中每个元素增加 1 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>答案保证在 32 位有符号整数以内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [1,2,3,2,1]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们需要至少 3 次操作从 intial 数组得到 target 数组。\n",
    "[0,0,0,0,0] 将下标为 0 到 4&nbsp;的元素（包含二者）加 1 。\n",
    "[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。\n",
    "[1,2,2,2,1] 将下表为 2 的元素增加 1 。\n",
    "[1,2,3,2,1] 得到了目标数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [3,1,1,2]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>(initial)[0,0,0,0] -&gt; [1,1,1,1] -&gt; [1,1,1,2] -&gt; [2,1,1,2] -&gt; [3,1,1,2] (target) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [3,1,5,4,2]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>(initial)[0,0,0,0,0] -&gt; [1,1,1,1,1] -&gt; [2,1,1,1,1] -&gt; [3,1,1,1,1] \n",
    "                                  -&gt; [3,1,2,2,2] -&gt; [3,1,3,3,2] -&gt; [3,1,4,4,2] -&gt; [3,1,5,4,2] (target)。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>target = [1,1,1,1]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= target.length &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= target[i] &lt;= 10^5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-increments-on-subarrays-to-form-a-target-array](https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-increments-on-subarrays-to-form-a-target-array](https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2,1]', '[3,1,1,2]', '[3,1,5,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        ans, n = target[0], len(target)\n",
    "        for i in range(1, n):\n",
    "            ans += max(target[i] - target[i-1], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        ans = target[0]\n",
    "        pre = ans\n",
    "        for num in target[1:]:\n",
    "            if num < pre:\n",
    "                pre= num\n",
    "                continue\n",
    "            else:\n",
    "                ans += num-pre\n",
    "                pre = num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        t = -1\n",
    "        length = len(target)\n",
    "        for i in range(length-1):\n",
    "            if target[i] > target[i+1]:\n",
    "                t = target[i]\n",
    "                t_number = i\n",
    "                break\n",
    "        if t == -1:\n",
    "            t = max(target)\n",
    "            return t\n",
    "\n",
    "        for j in range(t_number, length-1):\n",
    "            if target[j] > target[j+1]:\n",
    "                continue\n",
    "            else:\n",
    "                t += target[j+1] - target[j]\n",
    "                continue\n",
    "\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        stack = [0]\n",
    "        res = 0\n",
    "        for e in target:\n",
    "            if stack[-1] < e:\n",
    "                res += e - stack[-1]\n",
    "            else:\n",
    "                while len(stack) > 0 and e <= stack[-1]:\n",
    "                    stack.pop()\n",
    "            stack.append(e)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        stack = [0]\n",
    "        n = len(target)\n",
    "        res = 0\n",
    "        cur_min, cur_max = 0,0\n",
    "\n",
    "        for num in target:\n",
    "            if num>=stack[-1]:\n",
    "                stack.append(num)\n",
    "                cur_max = max(cur_max, num)\n",
    "            elif num<stack[-1]:\n",
    "                res += (cur_max-cur_min)\n",
    "                stack.append(num)\n",
    "                cur_max, cur_min = num, num \n",
    "        if stack:\n",
    "            res += (cur_max-cur_min)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        return target[0] + sum(max(y - x, 0) for x, y in pairwise(target))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        # 从initial到target的过程就是不断的对区间进行操作的过程（不断的对区间加上1）\n",
    "        # 那么想到差分数组，一开始Initial的差分数组就是全零，然后经过一定数量的操作次数后\n",
    "        # 变成target的差分数组。那么操作次数，就是target的差分数组里面的正数之和\n",
    "        # 因为差分数组里左端点是一定包括的，但是右端点有可能超出数组右边。\n",
    "        # 又因为本题每次都是加1，所以正数的总和，就是区间操作的次数\n",
    "        res = target[0]\n",
    "        for i in range(1,len(target)):\n",
    "            res += max(0, target[i] - target[i-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        ans = target[0]\n",
    "        for i in range(1,n):\n",
    "            ans += max(target[i]-target[i-1],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        rs = target[0]\n",
    "        # 2 3 4 5 3 2 1\n",
    "        for i in range(1, n):    \n",
    "            if target[i-1] < target[i]:\n",
    "                rs += (target[i] - target[i-1]) \n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\r\n",
    "        #思考第一个元素\r\n",
    "        pre = 0\r\n",
    "        res = 0  \r\n",
    "        for x in  target:\r\n",
    "            if x > pre:\r\n",
    "                res += x - pre \r\n",
    "            pre = x \r\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        st = [0]\n",
    "        ans =0\n",
    "        for x in target:\n",
    "            if x == st[-1]:\n",
    "                continue\n",
    "            elif x > st[-1]:\n",
    "                st.append(x)\n",
    "            else:\n",
    "                ans+=st[-1]-x\n",
    "                while st[-1]>=x:\n",
    "                    st.pop()\n",
    "                st.append(x)\n",
    "        return ans+st[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        re,left = 0,0\n",
    "        for n in target:\n",
    "            if n>left: re += (n-left)\n",
    "            left = n\n",
    "        return re\n",
    "\n",
    "# 作者：skay2002\n",
    "# 链接：https://leetcode.cn/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/solutions/346830/jiu-shi-kan-bian-hua-liang-de-hardping-ji-tai-kai-/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        return sum(max(target[i+1]-target[i],0) for i in range(len(target)-1)) + target[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        ans = target[0]\n",
    "        for i in range(1, n):\n",
    "            ans += max(target[i] - target[i - 1], 0)\n",
    "        return ans               \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "\n",
    "\n",
    "        n = len(target)\n",
    "        \n",
    "        cut = 0\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if target[i]>cut:\n",
    "                ans += target[i]-cut\n",
    "                cut = target[i]\n",
    "            else:\n",
    "                cut = target[i]\n",
    "        return ans \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        return sum(max(target[i+1]-target[i],0) for i in range(len(target)-1)) + target[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        ans = target[0]\n",
    "        for i in range(1, n):\n",
    "            ans += max(target[i] - target[i-1], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        ans = target[0]\n",
    "        for i in range(1, len(target)):\n",
    "            if target[i] > target[i-1]:\n",
    "                ans += target[i] - target[i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        ans = target[0]\n",
    "        for i in range(1, n):\n",
    "            ans += max(target[i] - target[i - 1], 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        re = target[0]\n",
    "        for i in range(1, len(target)):\n",
    "            re += max(0, target[i] - target[i - 1])\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        ans = target[0]\n",
    "        p = target[0]\n",
    "        for t in target:\n",
    "            if p >= t:\n",
    "                p = t\n",
    "            else:\n",
    "                ans += t - p\n",
    "                p += t - p\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        ans = target[0]\n",
    "        for i in range(1,len(target)):\n",
    "            ans += max(target[i]-target[i-1],0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for t in target:\n",
    "            ans += max(0, t-pre)\n",
    "            pre = t\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        ans = target[0]\n",
    "        for i in range(1, len(target)):\n",
    "            ans += max(target[i] - target[i - 1], 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import reduce\r\n",
    "class Solution:\r\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\r\n",
    "        n = len(target)\r\n",
    "        return reduce(lambda x, i: x + max(0, target[i] - target[i - 1]), range(1, n), target[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        l = []\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if l and target[i] < l[-1]:\n",
    "                ans += l[-1] - target[i]\n",
    "                while l and target[i] < l[-1]:\n",
    "                    l.pop()\n",
    "            l.append(target[i])\n",
    "        ans += l[-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = []\n",
    "        for x in target:\n",
    "            if st and st[-1] == x: continue\n",
    "            while st and st[-1] > x:\n",
    "                y = st.pop()\n",
    "                ans += y-(max(x,st[-1]) if st else x)\n",
    "            st.append(x)\n",
    "        ans += st[-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        dp = [0]*n\n",
    "        dp[0] = target[0]\n",
    "        for i in range(1, n):\n",
    "            if target[i] > target[i-1]:\n",
    "                dp[i] = dp[i-1] + target[i] - target[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[n-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n=len(target)\n",
    "        dp=[0]*n\n",
    "        dp[0]=target[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i]=dp[i-1]\n",
    "            if target[i]>target[i-1]:\n",
    "                dp[i]+=target[i]-target[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        dp = [0 for _ in range(len(target))]\n",
    "        dp[0] = target[0]\n",
    "        for i in range(1, len(target)):\n",
    "            if target[i] <= target[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1] + target[i] - target[i-1]\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        n = len(target)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = target[0]\n",
    "        for i in range(1, n):\n",
    "            if target[i] <= target[i-1]:\n",
    "                dp[i] = dp[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]+target[i]-target[i-1]\n",
    "        return dp[n-1]\n",
    "\n",
    "            \n",
    "        #find min of arr, minus all by min, add ret by min\n",
    "        # self.ret = 0\n",
    "        # def divide(left, right):\n",
    "        #     minVal = min(target[left:right+1])\n",
    "        #     self.ret+=minVal\n",
    "        #     for i in range(left, right+1):\n",
    "        #         target[i]-=minVal\n",
    "        #     leftPtr, rightPtr = left, left\n",
    "        #     while rightPtr <= right:\n",
    "        #         if target[rightPtr] == 0: \n",
    "        #             rightPtr+=1\n",
    "        #             leftPtr=rightPtr\n",
    "        #             continue\n",
    "        #         while rightPtr <= right and target[rightPtr] != 0:\n",
    "        #             rightPtr+=1\n",
    "        #         divide(leftPtr, rightPtr-1)\n",
    "        # divide(0, len(target)-1)\n",
    "        # return self.ret\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        dp = [0] * len(target)\n",
    "        dp[0] = target[0]\n",
    "        for i in range(1, len(target)):\n",
    "            if target[i] > target[i-1]:\n",
    "                dp[i] = dp[i-1] + target[i] - target[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        dp = [0] * len(target)\n",
    "        dp[0] = target[0]\n",
    "        for i in range(1,len(target)):\n",
    "            if target[i] > target[i-1]:\n",
    "                dp[i] = dp[i-1] + target[i] - target[i-1]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        t = []\n",
    "        prev = 0\n",
    "        for i in target:\n",
    "            if i == prev:\n",
    "                continue\n",
    "            t.append(i)\n",
    "            prev = i\n",
    "        # t为去掉连续的重复值后的target\n",
    "        n = len(t)\n",
    "        if n == 1:\n",
    "            return t[0]\n",
    "        # 数组索引处是否为极大值\n",
    "        check = [t[0] > t[1]] + [t[i - 1] < t[i] and t[i] > t[i + 1] for i in range(1, n - 1)] + [t[-1] > t[-2]]\n",
    "        idx = check.index(True)\n",
    "        MIN = ans = t[idx]\n",
    "        for i in range(idx + 1, n):\n",
    "            if check[i]:\n",
    "                ans += t[i] - MIN\n",
    "                MIN = t[i]\n",
    "            MIN = min(MIN, t[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOperations(self, target: List[int]) -> int:\n",
    "        target=[0]+target\n",
    "        return sum([target[i]-target[i-1] if target[i]-target[i-1]>0 else 0 for i in range(1,len(target))])\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
